The Internet includes a network of interconnected routers that route data packets over one or more links between a source Internet Protocol (IP) address and a destination IP address. Successful routing of data packets requires that a logical path (a collection of one or more links) exist in the network between the source IP address and destination IP address for that packet. Based on the contents of its routing table, each router along the path determines the best path on which to send each packet in order to deliver the packets to the ultimate destination. Assuming the network possesses sufficient physical redundancy (e.g., multiple routers, multiple links), the network can dynamically redefine paths using protocols such as the Border Gateway Protocol (BGP) or Open Shortest Path First (OSPF) protocol, in case of a router or link failure. The use of such protocols ensures that no one router or link failure disrupts the flow of packets between a source IP address and destination IP address.
When there is a relatively large volume of traffic between two network switches, it is helpful to link several ports of the two switches together to provide more than one path between the two switches. Multiple links can be provided by separate transmission lines, each connecting an output port of one switch to an input port of another switch. Such links could also be provided by a high speed multiplexer/demultiplexer system connected to several input/output ports of each switch. A multiplexer at one end of a transmission line receives data packet transmissions concurrently from several output ports of one switch and multiplexes them onto the high speed transmission line. A demultiplexer at the opposite end of the transmission line separates the packets and routes them concurrently into separate input ports of another switch. The two switches, however, simply view the multiplexer/demultiplexer system as several separate paths.
In order to make efficient use of multiple paths between network switches it is desirable to distribute the transmission load evenly over those multiple paths. But load balancing has been problematic. Recall that a switch input port receiving a packet consults an address translation system to find out which switch output port is to receive the packet. Although the address translation system may assign many different network destination addresses to the same switch output port, it can assign each network address to one and only one output port. Thus, for example, when 10 output ports of a first switch are connected to 10 input ports of a second switch by 10 transmission lines, the first switch can forward an incoming data packet addressed to a network station connected to the second switch via only one of the 10 output ports. If that particular output port is busy, packet transmission is blocked and the input port has to store the packet until the particular output port is available, even if the other nine output ports linked to the second switch are idle.
Conventional load balancing schemes calculate a distribution ratio based on the current actual load on each port. New flows are subsequently assigned to ports using this calculated distribution ratio whereby new flows are assigned to the least loaded ports. This tends to make the system highly unstable because of the bursty nature of Internet traffic and a distribution ratio using only the instant load on the system tends to either overshoot or undershoot the target traffic rate. This is commonly termed as ‘hunting’ and can cause drastic reduction in the throughput of the system.
Accordingly, what is needed is a method and system that addresses the above-described short-comings of conventional load balancing techniques. The method and system should be simple, cost effective and capable of being easily adapted into existing technology. The present invention addresses such a need.